package com.caoyanan.algorithm.question.zuoTraining.training003.class07;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.HashMap;
import java.util.Map;

/**
 * 无重复最长子串
 *
 * 子串是abc，长度为3
 * bbbbb，答案是b，长度为1
 * pwwkew，答案是wke，长度是3
 * 要求:答案必须是子串，"pwke" 是一个子字符序列但不是一个子字符串。
 * @author: caoyanan
 * @time: 2021/5/20 2:55 下午
 */
public class Question04_NoRepeatCharLongestSubString {

    public static void main(String[] args) {

        int count = 10000;
        String bbdbbbedaeeb = noRepeatCharLongestSubString("bbdbbbedaeeb");
        System.out.println(bbdbbbedaeeb);

        for (int i = 0; i < count; i++) {
            String str = LogarithmInputGenerator.getInstance()
                    .generateLowerLetterString(12, 5);
            String result = noRepeatCharLongestSubString(str);
            System.out.printf("输入字符串 %s 的最长无重复子串为 %s", str, result);
            System.out.println();
        }


    }

    /**
     * 考虑 以i位置结尾的子串，最长连续不重复的字符的开始位置是 dp[i]
     * dp[i]的值与两个有关，1是arr[i]上次出现的位置+1，和dp[i-1]谁距离自己近
     * @param str
     * @return
     */
    private static String noRepeatCharLongestSubString(String str) {
        char[] chars = str.toCharArray();
        int[] dp = new int[chars.length];
        Map<Character, Integer> map = new HashMap<>(chars.length);
        dp[0] = 0;
        map.put(chars[0], 0);

        int longestEndIndex = 0;
        int longestSubStringLength = 1;
        for (int i = 1; i < chars.length; i++) {
            dp[i] = Math.max(dp[i - 1], map.getOrDefault(chars[i], -1) + 1);
            map.put(chars[i], i);
            if (i - dp[i] + 1 > longestSubStringLength) {
                longestSubStringLength = i - dp[i] + 1;
                longestEndIndex = i;
            }
        }
        return str.substring(dp[longestEndIndex], dp[longestEndIndex] + longestSubStringLength);
    }
}
